`timescale 1ns/1ns

module lcm#(
           parameter DATA_W = 8)
       (
           input [DATA_W - 1: 0] A,
           input [DATA_W - 1: 0] B,
           input vld_in,
           input	rst_n,
           input clk,
           output	wire	[DATA_W * 2 - 1: 0] lcm_out,
           output	wire [DATA_W - 1: 0]	mcd_out,
           output	reg	vld_out
       );
// 题目要求求解两个数的最小公倍数，而最小公倍数可以通过两个数的乘积除以两个数的最小公约数得到。
//  乘法是容易计算的，所以问题变成如何求解最大公约数。可以采用辗转相减法求解，例如 ：两个自然数35和14，
// 用大数减去小数，(35,14)->(21,14)->(7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，
// 再做一次相减，结果为0，这样也就求出了最大公约数7。
reg	[DATA_W * 2 - 1: 0]	mcd, a_buf, b_buf;
reg [DATA_W * 2 - 1: 0]	mul_buf;
reg	mcd_vld;
reg	[1: 0]	cur_st, nxt_st;
parameter IDLE = 2'b00, S0 = 2'b01, S1 = 2'b10, S2 = 2'b11;
//两段式状态机
always @(posedge clk or negedge rst_n)
	if (!rst_n)
		cur_st <= IDLE;
	else
		cur_st <= nxt_st;
always @(posedge clk or negedge rst_n)
	if (!rst_n)
		begin
			nxt_st <= IDLE;
			mcd	<= 0;
			mcd_vld <= 0;
			a_buf <= 0;
			b_buf <= 0;
			mul_buf <= 0;
			vld_out <= 1'b0;
		end
	else
		begin
			case (cur_st)
				IDLE:
					if (vld_in)
						begin
							a_buf <= A;
							b_buf <= B;
							nxt_st <= S0;
							mul_buf <= A * B;
							mcd_vld <= 0;
							vld_out <= 1'b0;
						end
					else
						begin
							nxt_st <= IDLE;
							mcd_vld <= 0;
							vld_out <= 1'b0;
						end
				S0:
					if (a_buf != b_buf)
						begin
							if (a_buf > b_buf)
								begin
									a_buf <= a_buf - b_buf;
									b_buf <= b_buf;
								end
							else
								begin
									b_buf <= b_buf - a_buf;
									a_buf <= a_buf;
									vld_out <= 1'b0;
								end
							nxt_st <= S0;
						end
					else
						begin
							nxt_st <= S1;
							vld_out <= 1'b0;
						end
				S1:
					begin
						mcd <= b_buf;
						mcd_vld <= 1'b1;
						nxt_st	<= IDLE;
						vld_out <= 1'b1;
					end
				default:
					begin
						nxt_st <= IDLE;
						vld_out <= 1'b0;
					end
			endcase
		end

assign mcd_out = mcd;
assign lcm_out = mul_buf / mcd;
endmodule
